/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LianBao
 * Date: 2024-09-15
 * Time: 9:09
 */
public class MyLinkedList {
    public ListNode head;//头
    public ListNode tail;//尾

    static class ListNode {
        int val;//值
        public ListNode prev;//前驱
        public ListNode next;//后继

        public ListNode(int val) {
            this.val = val;
        }
    }


    //获取长度
    public int size() {
        if (head == null) {
            return 0;
        }
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            cur = cur.next;
            count++;
        }
        return count;
    }

    //头插
    public void addFirst(int val) {
        ListNode newNode = new ListNode(val);//新的结点
        if (head == null) {
            //没有结点
            head = newNode;
            tail = newNode;
            return;
        }

        newNode.next = head;
        head.prev = newNode;
        head = newNode;

    }

    //尾插
    public void addLast(int val) {
        ListNode newNode = new ListNode(val);//新的结点
        if (head == null) {
            //没有结点
            head = newNode;
            tail = newNode;
            return;
        }
        newNode.prev = tail;
        tail.next = newNode;
        tail = newNode;
    }

    //在Index位置插入
    public void addIndex(int val, int index) {
        if (index < 0 || index > size()) {
            throw new IndexNotLegalException("Index不合法");
        }

        if (index == 0) {
            addFirst(val);
            return;
        }
        if (index == size()) {
            addLast(val);
            return;
        }
        ListNode cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        ListNode newNode = new ListNode(val);

        ListNode cP = cur.prev;
        newNode.next = cur;
        newNode.prev = cP;
        cP.next = newNode;
        cur.prev = newNode;


    }

    //是否包含
    public boolean contains(int key) {
        if (head == null) {
            return false;
        }
        ListNode cur = head;

        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }

        return false;
    }

    //删除第一个值为val的结点
    public void remove(int key) {
        if (head == null) {
            return;
        }

        //如果是第一个结点
        if (head.val == key) {
            head = head.next;
            head.prev = null;
            return;
        }

        //如果是最后一个结点
        if (tail.val == key) {
            tail = tail.prev;
            tail.next = null;
            return;
        }

        ListNode del = head;
        while (del != null) {
            if (del.val == key) {
                break;
            }
            del = del.next;
        }
        if (del == null) {
            //del为空,说明没有要删除的结点
            return;
        }
        ListNode delP = del.prev;//要删除的结点的前驱
        ListNode delN = del.next;//要删除的结点的后继
        delP.next = delN;
        delN.prev = delP;
    }

    //删除所有值为val的结点
    public void removeAll(int key) {

        if (head == null) {
            return;
        }

        //处理前面部分全是key的情况
        while (head.val == key) {

            head = head.next;
            if (head == null) {
                return;
            }

        }
        head.prev = null;

        //处理后面部分全是key
        while (tail.val == key) {

            tail = tail.prev;
            if (tail == null) {
                return;
            }
        }
        tail.next = null;


        //中间部分
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) {
                ListNode del = cur;
                del.prev.next = del.next;
                del.next.prev = del.prev;
            }
            cur = cur.next;
        }

    }

    //清除整个链表
    public void clear() {
        if (head == null) {
            return;
        }
        ListNode cur = head;
    }

    //打印链表
    public void print() {
        ListNode cur = head;
        if (head == null) {
            System.out.println("null");
            return;
        }
        while (cur != null) {
            System.out.printf(cur.val + "->");
            cur = cur.next;
        }
        System.out.println("null");
    }

}
